#include <stdio.h>

#define NMAX 10000
#define DEQ_DATA_TYPE int

/* {{{ DEQ */
#ifndef DEQUEUE_H
#define DEQUEUE_H

#ifndef NMAX
const int NMAX = 500000;
#endif

#ifndef DEQ_DATA_TYPE
#define DEQ_DATA_TYPE int
#endif

struct Dequeue {
	DEQ_DATA_TYPE data[NMAX];
	int head;
	int size;
};
#endif

extern void
Clear(struct Dequeue * d)
{
	d->size = 0;
	d->head = 0;
}



extern int
PushFront(struct Dequeue * d, int key)
{
	if (d->size < NMAX) {
		if (d->head == 0)
			d->head = NMAX-1;
		else
			--d->head;
		d->data[d->head] = key;
		d->size++;
		return 0; /* OK */
	} else {
		return 1; /* deq overflow */
	}
}



extern int
PushBack(struct Dequeue * d, int key)
{
	if (d->size < NMAX) {
		d->data[ (d->head + d->size) % NMAX ] = key;
		++d->size;
		return 0;
	} else {
		return 1; /* deq overflow */
	}
}



extern DEQ_DATA_TYPE
PopFront(struct Dequeue * d)
{
	if (d->size > 0) {
		--d->size;
		if (d->head == NMAX)
			d->head = 0;
		return d->data[ d->head++ % NMAX ];
	} else {
		return 0; /* do not touch head and size */
	}
}



extern DEQ_DATA_TYPE
PopBack(struct Dequeue * d)
{
/*	if (d->size) {
		--d->size;
		return d->data[ (d->head + d->size + 1) % NMAX ];
	}
	return 0; */
	return d->size ? d->data[ (d->head + (--d->size)) % NMAX ] : 0;
}



extern DEQ_DATA_TYPE
Front(const struct Dequeue * d)
{
	return d->data[d->head];
}



extern DEQ_DATA_TYPE
Back(const struct Dequeue * d)
{
	return d->data[(d->head + d->size - 1) % NMAX];
}



extern unsigned char
IsEmpty(const struct Dequeue * d)
{
	return d->size ? false : true;
}
/* }}} */


int
main(void)
{
	struct Dequeue bookshelf;
	int cmd, book;
	int chk = 0;
	register int i = 0;

	(void)freopen("bookshelf.in", "r", stdin);
	(void)freopen("bookshelf.out", "w", stdout);
	bookshelf.size = 0;
	bookshelf.head = 0;

	while (scanf("%d", &cmd), cmd != 0) {
		if (cmd == 1) {
			(void)scanf("%d", &book);
			chk = PushFront(&bookshelf, book);
		} else if (cmd == 2) {
			(void) scanf("%d", &book);
			chk = PushBack(&bookshelf, book);
		} else if (cmd == 3) {
			printf("%d\n", PopFront(&bookshelf));
		} else if (cmd == 4) {
			printf("%d\n", PopBack(&bookshelf));
		} else {
			fprintf(stderr, "???\t---\ti=%d, cmd=%d\n", i, cmd);
		}
		if (chk) {
			fprintf(stderr, "DEQ overflow detected.\n\ti=%d, cmd=%d.\n", i, cmd);
			chk = 0;
		}
		fflush(stdout);
		fflush(stderr);
		++i;
	}
	return 0;
}

// vim: foldmethod=marker:
